/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/median-of-two-sorted-arrays
   @Language: C++
   @Datetime: 19-05-17 10:57
   */

// Method 1, Time O(log(m+n)), Space O(1)
class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		if(nums1.size()>nums2.size()) return findMedianSortedArrays(nums2,nums1);
		int m=nums1.size(), n=nums2.size();
		for(int left=0, right=m; left<=right;){
			int i=(left+right)/2;
			int j=(m+n+1)/2-i;
			if(i<right && nums2[j-1]>nums1[i]) left=i+1;
			else if(i>left && nums1[i-1]>nums2[j]) right=i-1;
			else{
				int maxl=0;
				if(i==0) maxl=nums2[j-1];
				else if (j==0) maxl=nums1[i-1];
				else maxl=max(nums1[i-1],nums2[j-1]);
				if((m+n)%2) return maxl;
				int minr=0;
				if(i==m) minr=nums2[j];
				else if(j==n) minr=nums1[i];
				else minr=min(nums1[i],nums2[j]);
				return (maxl+minr)/2.0;
			}
		}
		return 0;
	}
};


// Method 2, merge, Time O(m+n), Space O(1)
class Solution {
public:
	double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
		int m=A.size(), n=B.size();
		int ab[2]={0,0};
		for(int i=0, j=0, k=0; (i<m || j<n) && k<=(m+n)/2; ++k){
			swap(ab[0],ab[1]);
			if(i>=m) ab[1]=B[j++];
			else if(j>=n) ab[1]=A[i++];
			else ab[1]=A[i]<B[j]?A[i++]:B[j++];
		}
		if((m+n)&1) return ab[1];
		else return (ab[0]+ab[1])/2.0;
	}
};
